#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 struct ListNode {
      int val;
     struct ListNode *next;
  };
 


//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    struct ListNode* head = NULL;
//    struct ListNode* p = NULL;
//
//    while (list1 && list2)
//    {
//        if (head == NULL)
//        {
//            if (list1->val > list2->val)
//                head = list1;
//            else
//                head = list2;
//            p = head;
//        }
//        else {
//            if (list1->val > list2->val)
//                p->next = list1;
//            else
//                p->next = list2;
//            p = p->next;
//        }
//        list1 = list1->next;
//        list2 = list2->next;
//    }
//    if (list1 == NULL)
//        p->next = list2;
//    else
//        p->next = list1;
//    return head;
//}
 //struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
 //    struct ListNode* head = NULL;
 //    struct ListNode* p = NULL;

 //    while (list1 && list2)
 //    {
 //        if (head == NULL)
 //        {
 //            if (list1->val > list2->val)
 //                head = list1;
 //            else
 //                head = list2;
 //            p = head;
 //        }
 //        else {
 //            if (list1->val > list2->val)
 //                p->next = list1;
 //            else
 //                p->next = list2;
 //            p = p->next;
 //        }
 //        list1 = list1->next;
 //        list2 = list2->next;
 //    }
 //    if (list1 == NULL)
 //        p->next = list2;
 //    else
 //        p->next = list1;
 //    return head;
 //}
 struct ListNode* removeElements(struct ListNode* head, int val) {
     struct ListNode* cur = head;
     struct ListNode* new = NULL;
     struct ListNode* tail = NULL;
     struct ListNode* p = NULL;
     while (cur)
     {
         if (cur->val != val && new == NULL)
         {
             new = cur;
             tail = new->next;
             cur = cur->next;
         }
         else if (cur->val != val)
         {
             tail = cur;
             tail = tail->next;
             cur = cur->next;
         }
         else
         {
             p = cur;
             cur = cur->next;

             free(p);

         }

     }
     tail = NULL;
     return new;
 }
 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
     if (list1 == NULL)
         return list2;
     if (list2 == NULL)
         return list1;
     struct ListNode* head = NULL;
     struct ListNode* p = NULL;

     while (list1 && list2)
     {
         if (head == NULL)
         {
             if (list1->val > list2->val)
             {
                 head = list2;
                 list2 = list2->next;
             }
             else
             {
                 head = list1;
                 list1 = list1->next;
             }
             p = head;
         }
         else {
             if (list1->val < list2->val)
             {
                 p->next = list1;
                 list1 = list1->next;
             }
             else
             {
                 p->next = list2;
                 list2 = list2->next;
             }
             p = p->next;
         }

     }
     if (list2)
         p->next = list2;
     if (list1)
         p->next = list1;
     return head;
 }
 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
     if (list1 == NULL)
         return list2;
     if (list2 == NULL)
         return list1;
     struct ListNode* head = NULL;
     struct ListNode* p = NULL;

     while (list1 && list2)
     {
         if (list1->val > list2->val)
         {
             if (head == NULL)
             {
                 head = p = list2;
                 list2 = list2->next;
             }
             else
             {
                 p->next = list2;
                 list2 = list2->next;
                 p = p->next;
             }
         }
         else {
             if (head == NULL)
             {
                 head = p = list1;
                 list1 = list1->next;
             }
             else
             {
                 p->next = list1;
                 list1 = list1->next;
                 p = p->next;
             }
         }

     }
     if (list2)
         p->next = list2;
     if (list1)
         p->next = list1;
     return head;
 }